// 字典的封装
class Dictionay {
  constructor () {
    this.items = {}
  }
  // 判断字典中是否含有key
  has (key) {
    return this.items.hasOwnProperty(key)
  }
  //在字典中添加键值对
  set (key, value) {
    this.items[key] = value
  }
  // 删除指定的key
  remove (key) {
    if (!this.has(key)) return false
    delete this.items[key]
  }
  // 获取指定的key
  get (key) {
    return this.has(key) ? this.items[key] : undefined
  }
  // 获取所有的value
  keys () {
    return Object.values(this.items)
  }
  // 获取字典中键值对的个数
  size () {
    return this.keys().length
  }
  // 清空
  clear () {
    this.items = {}
  }
}
// 图类的封装 (邻接表、邻接矩阵)___ 邻接表
class Graph {
  constructor () {
    this.vertexes = [] // 存储顶点
    this.adjList = new Dictionay() // 存储边的信息(邻接表)
  }
  // 添加顶点
  addVertex (val) {
    // 添加点
    this.vertexes.push(val)
    // 添加点的关系 使用邻接矩阵方法:结构字典
    this.adjList.set(val, [])
  }
  // 添加边
  addEdge (val1, val2) {
    // 边是两个顶点的边
    this.adjList.get(val1).push(val2)
    this.adjList.get(val2).push(val1)
  }
  // 输出图结构
  toString () {
    let res = ''
    for (let i = 0; i < this.vertexes.length; i++) {
      res += this.vertexes[i] + "->"
      let adj = this.adjList.get(this.vertexes[i])
      for (let j = 0; j < adj.length; j++) {
        res += adj[j] + ""
      }
      res += "\n"
    }
    return res
  }
  // 初始化顶点的颜色
  _initializeColor () {
    // 白色:表示该顶点还没有被访问过
    // 灰色: 表示该顶点被访问过 但并未被探索过
    // 黑色" 表示该顶点被访问过且被完全探索过
    let colors = []
    for (let i = 0; i < this.vertexes.length; i++) {
      colors[this.vertexes[i]] = 'white'
    }
    return colors
  }
  // 遍历图:完全探索一个顶点要求我们便查看该顶点的每一条边
  // BFS: 从指定的第一个顶点遍历图,先访问其所有的相邻点 就像访问图的一层
  bfs (handle) {
    // 广度优先搜索
    // 1.初始化所有颜色
    let color = this._initializeColor()
    console.log(color, 'color')
    // 2. 创建一个队列
    let queue = []
    // 3.将传入的顶点放入队列
    queue.push(this.vertexes[0])
    // 4.依赖队列操作数据 队列不为空时一直持续
    while (queue.length > 0) {
      // 4.1 拿到队头
      let qVal = queue.shift() // 队头即数组第一个元素
      // 4.2 拿到队头所关联的点并设置为访问中状态
      let qAdj = this.adjList.get(qVal)
      color[qVal] = 'gray'
      // 4.3 将队头所关联的点添加到队尾
      for (let i = 0; i < qAdj.length; i++) {
        let a = qAdj[i]
        if (color[a] === 'white') {
          color[a] = 'gray'
          queue.push(a)
        }
      }
      // 4.4 设置访问完的点为黑色
      color[qVal] = 'black'
      if (handle) {
        handle(qVal)
      }
    }
  }
  // 深度优先遍历 
  dfs (handle) {
    // 1.初始化颜色
    let color = this._initializeColor()
    // 2.遍历所有顶点 开始访问
    for (let i = 0; i < this.vertexes.length; i++) {
      if (color[this.vertexes[i]] === 'white') {
        this._dfsVisit(this.vertexes[i], color, handle)
      }
    }
  }
  _dfsVisit (val, color, handle) {
    // 1.将颜色设置为访问中
    color[val] = 'gray'
    // 2.执行相应的回调
    if (handle) {
      handle(val)
    }
    // 3.拿与该点相邻的点 对每个点操作
    let adj = this.adjList.get(val)
    for (let i = 0; i < adj.length; i++) {
      let w = adj[i]
      // 如果相邻点未访问状态 则开始访问
      if (color[w] === 'white') {
        this._dfsVisit(w, color, handle)
      }
    }
    // 4. 处理完后设置为访问过该节点
    color[val] = 'black'
  }
}
const graph = new Graph()
let myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
for (let i = 0; i < myVertexes.length; i++) {
  graph.addVertex(myVertexes[i])
}
// 添加边
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
console.log(graph.toString());
// 调用广度优先算法
let result = ""
graph.bfs(function (v) {
  result += v + " "
})
console.log(result);
let dfsRst = ''
graph.dfs(function (v) {
  dfsRst += v + ' '
})
console.log(dfsRst);